A learning based approach to predict shortest-path distances

Abstract

Shortest-path distances on road networks have many applications such as finding nearest places of interest (POI) for travel recommendations. To compute a shortest-path distance, traditional approaches traverse the road network to find the shortest path and return the path length. When the distances are needed first (e.g., to rank POIs) while the shortest paths may be computed later (e.g., after a POI is chosen), one may precompute and store the distances, and answer distance queries by simple lookups. This approach, however, falls short in the worst-cast space cost – O(n2) for n vertices even with various optimizations. To address these limitations, we propose to learn an embedding for every..